package com.yincb.fibo;

import org.junit.Test;

public class FiboDemo {
    int[] data;
    /**
     * 斐波那契数列:
     *  1 1 2 3 5 8 13 21
     *  n>2 f(n) = f(n-1)+f(n-2)
     */
    // 新能最差
    public int recusive(int n){
        if(n<=2){
            return 1;
        }
        return recusive(n-1)+recusive(n-2);
    }

    // 循环优化
    public int  noRecusive(int n) {
        int a =1;
        int b =1;
        int c = 0;
        for (int i = 3; i <= n; i++){
            c=a+b;
            a=b;
            b=c;
        }
        return c;
    }
    // 缓存优化 data = new int[]
    public int recusive2(int n){
        if(n<=2){
            return 1;
        }
        if(data[n] > 0){
            return data[n];
        }
        int res = recusive2(n-1)+recusive2(n-2);
        data[n] = res;
        return res;
    }

    /**
     * 尾递优化
     * pre  上一次结果
     * ppre 上上一次结果
     */
    public int tailRecusive(int n,int pre,int ppre){
        if(n<=2){
            return ppre;
        }
        return tailRecusive(n-1,ppre,pre+ppre);
    }

    @Test
    public void test_recusive(){
        long start = System.currentTimeMillis();
        for (int i = 1; i <= 45; i++) {
            System.out.println(i+"\t"+recusive(i));
        }
        System.out.println("耗时："+(System.currentTimeMillis()-start)+"ms");
    }

    @Test
    public void  test_noRecusive(){
        long start = System.currentTimeMillis();
        for (int i = 1; i <= 45; i++) {
            System.out.println(i+"\t"+noRecusive(i));
        }
        System.out.println("耗时："+(System.currentTimeMillis()-start)+"ms");
    }


    @Test
    public void test_recusive2(){
        long start = System.currentTimeMillis();
        for (int i = 1; i <= 45; i++) {
            data = new int[46];
            System.out.println(i+"\t"+recusive2(i));
        }
        System.out.println("耗时："+(System.currentTimeMillis()-start)+"ms");
    }


    @Test
    public void test_tailRecusive(){
        long start = System.currentTimeMillis();
        for (int i = 1; i <= 45; i++) {
            System.out.println(i+"\t"+tailRecusive(i,1,1));
        }
        System.out.println("耗时："+(System.currentTimeMillis()-start)+"ms");
    }

}
